11288. Pair the people

 

There are n people at a party. Each person can either join the dance as a single individual or as part of a pair with any other person. Find the number of different ways in which all n people can join the dance.

 

Input. One integer n (1 ≤ n ≤ 105).

 

Output. Print the number of different ways all n people can join the dance. Print the answer modulo 109 + 7.

 

Example. Let we have n = 3 people. They can dance in 4 different ways: {1,2,3}, {{1,2},3}, {1,{2,3}}, {{1,3},2}.

 

Sample input

Sample output

3

4

 

 

SOLUTION

dynamic programming

 

Algorithm analysis

Let f(n) represent the number of different ways that all n people can join the dance. For example,

·        f(1) = 1, one person dances by himself;

·        f(2) = 2, for two people, there are two options: either dance separately or as a pair;

 

Consider the n-th person:

·        If he dances alone, the remaining n – 1 people can join the dance in f(n – 1) ways.

·        The n-th person can choose any of the n – 1 people as a partner. The remaining n – 2 people can join the dance in f(n – 2) ways.

 

Thus we have the relation:

f(n) = f(n – 1) + (n – 1) * f(n – 2)

 

Example

Let there be n = 3 people. They can join the dance in 4 ways:

·        if the third person dances separately: {1, 2, 3}, {{1, 2}, 3};

·        if the third person dances in a pair:  {1, {2, 3}}, {2, {1, 3}}.

Compute f(3) using a formula:

f(3) = f(2) + 2 * f(1) = 2 + 2 * 1 = 4

 

Algorithm realization

Declare a modulo constant and an array to store the answers: dp[n] = f(n).

 

#define MOD 1000000007

long long dp[100001];

 

Read the input value of n.

 

scanf("%d", &n);

 

Compute the values sequentially for f(1), f(2), …, f(n), storing each result in the dp array.

 

dp[1] = 1; dp[2] = 2;

for (i = 3; i <= n; i++)

  dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD;

 

Print the answer.

 

printf("%lld\n", dp[n]);

 

Python realization

Declare the modulo constant MOD, which will be used for the calculations.

 

MOD = 1000000007

 

Read the input value of n.

 

n = int(input())

 

Declare a list for storing the results, where dp[n] = f(n).

 

dp = [0] * (n + 1)

 

Compute the values sequentially for f(1), f(2), …, f(n), storing each result in the dp array.

 

dp[1] = 1

if n > 1: dp[2] = 2

for i in range(3, n + 1):

  dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % MOD

 

Print the answer.

 

print(dp[n])